package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/3/26 13:37
 */
public class No77_组合 {
    public static void main(String[] args) {
        Solution77 solution77 = new Solution77();
        List<List<Integer>> combine = solution77.combine(4, 3);
        System.out.println(combine);
    }
}

class Solution77 {
    public List<List<Integer>> combine(int n, int k) {
        //创建map
        //key:元素,value:标记
        Map<Integer,String> checkMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            checkMap.put(i, "未使用");
        }
        List<Integer> sortData = new ArrayList<>();
        List<List<Integer>> 最终结果 = new ArrayList<>();
        combine(n, k, checkMap, sortData, 最终结果);
        return 最终结果;
        
    }

    //开始递归
    public void combine(int n, int k, Map<Integer, String> checkMap,
                        List<Integer> sortData,
                        List<List<Integer>> 最终结果) {
        
        if (k == 0) {
            //加值
            List<Integer> 排序数据复制 = new ArrayList<>(sortData);
            最终结果.add(排序数据复制);
            return;
        }

        for (Map.Entry<Integer, String> mapData : checkMap.entrySet()) {
            //这里比如:我想要1234,那么第一轮遍历迟早会拿到1,如果
            //不是1比如是4, 4不会开头
            //因此这里这样操作(知道是否是升序)

            //1
            int currentKey = mapData.getKey();
            if (checkMap.get(currentKey).equals("未使用")) {
                //currentKey,要跟已经遍历的值的最后一个比较(因为是升序)
                if (sortData.size() == 0 || sortData.get(sortData.size() - 1) < currentKey) {
                    //当前索引已经使用
                    checkMap.put(currentKey, "已使用");
                    //这说明sortData一定升序
                    sortData.add(currentKey);
                    //下一轮递归
                    combine(n, k - 1, checkMap, sortData, 最终结果);
                    //回溯
                    checkMap.put(currentKey, "未使用");
                    sortData.remove(sortData.size() - 1);
                }
            }

        }
    }
}



    //public List<List<Integer>> combine(int n, int k) {
    //    List<Integer> 已递归索引 = new ArrayList<>();
    //    List<Integer> data = new ArrayList<>();
    //    List<List<Integer>> 最终结果 = new ArrayList<>();
    //    Set<String> 去重器 = new HashSet<>();
    //    combine(n, k, 已递归索引, data, 最终结果, 去重器);
    //    return 最终结果;
    //}
    //
    ////data:k=0时的找出的数集合
    //public void combine(int n, int k,
    //                    List<Integer> 已递归索引,
    //                    List<Integer> data,
    //                    List<List<Integer>> 最终结果,
    //                    Set<String> 去重器) {
    //
    //    if (k == 0) {
    //        //说明可以加了,最终结果
    //        //值传递问题
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        
    //        //排序,强行浪费资源
    //        dataCopy.sort(new Comparator<Integer>() {
    //            @Override
    //            public int compare(Integer o1, Integer o2) {
    //                return o1 >= o2 ? 1 : -1;
    //            }
    //        });
    //        //去重字符串
    //        String base = "";
    //        //遍历dataCopy
    //        for (int d : dataCopy) {
    //            // 124  214 -> 1?2?4 
    //            base += d + "_随便什么";
    //        }
    //        
    //        //去重
    //        if (去重器.add(base)) {
    //            最终结果.add(dataCopy);
    //        }
    //        return;
    //    }
    //    
    //    for (int i = 1; i <= n; i++) {
    //        if (!已递归索引.contains(i)) {
    //            //记录已递归索引
    //            已递归索引.add(i);
    //            data.add(i);
    //            //下一轮递归
    //            combine(n, k - 1, 已递归索引, data, 最终结果, 去重器);
    //            //回溯
    //            已递归索引.remove(已递归索引.size() - 1);
    //            data.remove(data.size() - 1);
    //        }
    //    }
    //}







